package algorithm.leetcode;

import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author wuwen
 * @since 2023/12/19
 */
public class NO75_颜色分类 {
    public static void main(String[] args) {
        int[] test = {2,0};
        new SolutionPerformance().sortColors(test);
        System.out.println(Arrays.toString(test));
    }


    static class SolutionPerformance {
        public void sortColors(int[] handles) {
            int i = 0, j = 0, k = handles.length - 1;
            while (j <= k) {
                if (handles[j] == 0) {
                    swap(handles, i++, j++);
                } else if (handles[j] == 2) {
                    swap(handles, j, k--);
                } else {
                    j++;
                }
            }
        }
        private void swap(int[] array, int i, int j) {
            if (i == j) {
                return;
            }
            array[i] ^= array[j];
            array[j] ^= array[i];
            array[i] ^= array[j];
        }
    }

    static class SolutionUnderdog {
        public void sortColors(int[] handles) {
            Map<Integer, Integer> counter = Arrays.stream(handles).boxed().collect(Collectors.toMap(k -> k, v -> 1, (ov, nv) -> ++ov));
            System.out.println(counter);
            int offset, index = 0;
            for (int i = 0; i < 3; i++) {
                for (offset = 0; offset < counter.getOrDefault(i, 0); offset++) {
                    handles[index + offset] = i;
                }
                index += offset;
            }
        }
    }


    /**
     * 冒泡排序
     * 使用标志位来优化，如果一轮里面已经没有换过了，就直接跳出
     */
    static class SolutionBubble {
        public void sortColors(int[] handles) {
            boolean modified;
            for (int i = 0; i < handles.length - 1; i++) {
                modified = false;
                for (int j = 0; j < handles.length - 1 - i; j++) {
                    if (handles[j] > handles[j + 1]) {
                        modified = true;
                        handles[j] ^= handles[j + 1];
                        handles[j + 1] ^= handles[j];
                        handles[j] ^= handles[j + 1];
                    }
                }
                if (!modified) {
                    break;
                }
            }
        }
    }

    // 逐渐恢复自己的能力

    /**
     * 选择排序
     */
    static class SolutionSelect {
        public void sortColors(int[] handles) {
            for (int i = 0; i < handles.length; i++) {
                for (int j = i; j < handles.length; j++) {
                    if (handles[i] > handles[j]) {
                        handles[i] ^= handles[j];
                        handles[j] ^= handles[i];
                        handles[i] ^= handles[j];
                    }
                }
            }
        }
    }
}
